Error correcting codes have many uses and applications including increasing reliability of data storage and transmitting data over an unreliable channel. Many applications utilize codes such as Reed-Solomon codes for error correction with strong error correcting capacity (i.e., information-theoretic rather than probabilistic) as well as the simplicity of the algorithms and implementation. However, Reed-Solomon codes often require quadratic time in the input size to encode the input message. Indeed, although using fast Discrete Fourier Transform algorithms, k input symbols can be encoded to n output symbols in O(n(log n)2 log log n) operations in the finite field Fq—where this complexity can be reduced to O(n log2 n), for fields of characteristic 2, or even to O(n log n), when q is a specific type of prime—these algorithms are not practical for small n. In practice, using Horner's method to directly evaluate the underlying polynomial requires O(kn) field operations which is much more efficient for small n.
Several codes have been proposed to overcome this quadratic encoding overhead. For example, Tornado codes are erasure codes achieve an asymptotic performance of O(n log n) (where n is the number of input symbols) and encoding and decoding speeds 100 to 10000 times greater than Reed-Solomon codes. In addition, Luby Transform (LT)-codes are erasure codes that use a carefully crafted sparse bipartite graph to also achieve O(n log n) encoding and decoding overhead. Furthermore, Raptor codes (rapid tornado codes) are erasure codes that perform encoding and decoding in linear time (in n) and are currently the fastest performing codes. Online codes are erasure codes that also have linear time encoding and decoding. Unlike Reed-Solomon and Tornado codes, which are block or fixed-rate codes producing a fixed number of output code symbols, it is noted that LT, Raptor and Online codes are also fountain codes that can generate a practically unlimited number of output code symbols.
However, each of these efficient bipartite-graph based fountain codes—hereby, simply called fountain codes—is an erasure code, thus not an error-corrective code, and has been analyzed over a random (erasure) channel rather than an adversarial (corruption) channel. Indeed, an adversarial channel could prevent the receiver from ever decoding the message by selectively corrupting symbols (e.g., by corrupting any code symbol that has the first message symbol in it). This attack fundamentally undermines one of the benefits of fountain codes; namely, that if the receiver simply waits for more code symbols (and the sender keeps generating such symbols), the receiver can eventually decode the file.
A need remains for authenticated error correcting codes that are substantially secure against a computationally bounded, adversarial channel. A further need remains for authenticated error correcting codes that substantially prevent the above-described selective-corruption attack.